package error

//#link: https://leetcode-cn.com/problems/valid-parenthesis-string/
func checkValidString(s string) bool {
	h := heap{
		c: make([]byte, 0),
	}
	for _, b := range []byte(s) {
		//堆里面有东西
		if len(h.c) != 0 {
			if b == '*' {
				h.push(b)
				continue
			}
			pop := h.pop()
			if pop == '*' {
				h.push(pop)
			} else {
				if pop != b {
					continue
				} else {
					h.push(pop)
					h.push(b)
				}
			}

		} else {
			//队列为空则添加进去
			h.push(b)
		}
	}

	for len(h.c) > 0 {
		heapTop := h.pop()
		if len(h.c) > 0 {
			nextPop := h.pop()
			if heapTop == '*' || nextPop == '*' || nextPop != heapTop {
				continue
			} else {
				return false
			}
		} else {
			return false
		}
	}

	return len(h.c) == 0
}

type heap struct {
	c []byte
}

func (h *heap) push(c byte) {
	h.c = append(h.c, c)
}

func (h *heap) pop() byte {
	ans := h.c[len(h.c)-1]
	h.c = h.c[:len(h.c)-1]
	return ans
}
